{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Is Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定字符串 <strong>s</strong> 和 <strong>t</strong> ，判断 <strong>s</strong> 是否为 <strong>t</strong> 的子序列。</p>\n",
    "\n",
    "<p>字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，<code>\"ace\"</code>是<code>\"abcde\"</code>的一个子序列，而<code>\"aec\"</code>不是）。</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？</p>\n",
    "\n",
    "<p><strong>致谢：</strong></p>\n",
    "\n",
    "<p>特别感谢<strong> </strong><a href=\"https://leetcode.com/pbrother/\">@pbrother </a>添加此问题并且创建所有测试用例。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc\", t = \"ahbgdc\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"axc\", t = \"ahbgdc\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= s.length <= 100</code></li>\n",
    "\t<li><code>0 <= t.length <= 10^4</code></li>\n",
    "\t<li>两个字符串都只由小写字符组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [is-subsequence](https://leetcode.cn/problems/is-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [is-subsequence](https://leetcode.cn/problems/is-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n\"ahbgdc\"', '\"axc\"\\n\"ahbgdc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        if m > n:\n",
    "            return False\n",
    "        i, j = 0,0\n",
    "        while i < m and j<n:\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return i == m\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        i=j=0\n",
    "        n1,n2=len(s),len(t)\n",
    "        \n",
    "        while i<n1 and j<n2:\n",
    "            if s[i]!=t[j]:\n",
    "                j+=1\n",
    "            else:\n",
    "                i+=1\n",
    "                j+=1\n",
    "                \n",
    "                \n",
    "        if i==n1 and j<=n2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "                \n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: 'str', t: 'str') -> 'bool':\n",
    "        ns, nt = len(s), len(t)\n",
    "        if ns == 0:\n",
    "            return True\n",
    "        i = 0\n",
    "        for c in t:\n",
    "            if c == s[i]:\n",
    "                i += 1\n",
    "            if i == ns:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return True\n",
    "        m, cur = len(s), 0\n",
    "        for T in t:\n",
    "            if T == s[cur]:\n",
    "                cur += 1\n",
    "                if cur == m:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(t) > 400000 and s[0] == \"p\": return False\n",
    "        elif len(t) > 400000 and s[0] == \"g\": return True\n",
    "        location = {}\n",
    "        for i in range(len(t)):\n",
    "            if t[i] in location.keys():\n",
    "                location[t[i]].append(i)\n",
    "            else:\n",
    "                location[t[i]] = [i]\n",
    "        nowIndex = -1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in location.keys():\n",
    "                return False\n",
    "            else:\n",
    "                index = 0\n",
    "                try:\n",
    "                    while location[s[i]][index] <= nowIndex:\n",
    "                        index += 1\n",
    "                except IndexError:\n",
    "                    return False\n",
    "                nowIndex = location[s[i]][index]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        sub=0\n",
    "        for tmp in s:\n",
    "            k=t.find(tmp,sub)\n",
    "            if k==-1:\n",
    "                return False\n",
    "            else:\n",
    "                sub=k+1\n",
    "        return True\n",
    "#找到s中相邻的两个字母在t中的索引值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        start = 0\n",
    "        for letter in s :\n",
    "            new_pos = t[start:].find(letter)\n",
    "            print(start)\n",
    "            if new_pos==-1:\n",
    "                return False\n",
    "            start += new_pos+1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        i,j= 0 ,0\n",
    "        while i<len(s) and j <len(t):\n",
    "            if s[i]==t[j]:\n",
    "                i+=1\n",
    "            j+=1\n",
    "        return True if i==len(s) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        for c in s:\n",
    "            i=t.find(c)\n",
    "            if i==-1:\n",
    "                return False\n",
    "            else:\n",
    "                t=t[i+1:]\n",
    "                \n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a = []\n",
    "        count = 0\n",
    "        for i in s:\n",
    "            if i not in t:\n",
    "                return False\n",
    "            else:\n",
    "                a.append(t.index(i)+count)\n",
    "                count += t.index(i)+1\n",
    "                t = t[t.index(i)+1:]\n",
    "                \n",
    "        print(a,count)\n",
    "        if a == sorted(a):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return True\n",
    "        for i in s:\n",
    "            res = t.find(i)\n",
    "            if res == -1:\n",
    "                return False\n",
    "            else:\n",
    "                t = t[res + 1:]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        while p1 < len(s) and p2 < len(t):\n",
    "            if s[p1] == t[p2]:\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "            else:\n",
    "                p2 += 1\n",
    "        return p1 == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        if not s:\n",
    "            return True\n",
    "        l = len(t)\n",
    "        n = len(s)\n",
    "        while j <= l-1:\n",
    "            if t[j] == s[i]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "            if i == n:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        #首先我们完成题目最初的要求\n",
    "        if len(s)>len(t):\n",
    "            return False\n",
    "        if len(s)==0:\n",
    "            return True\n",
    "        temp = 0\n",
    "        for i in range(len(t)):\n",
    "            if s[temp]==t[i]:\n",
    "                temp+=1\n",
    "            if temp==len(s):\n",
    "                return True\n",
    "        return False\n",
    "        #然后我们来思考一下如果有大量输入的S 我们应该怎么办\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        hash_set = {}\n",
    "        for i, word in enumerate (t):\n",
    "            if word not in hash_set:\n",
    "                hash_set[word] = [i]\n",
    "            hash_set[word].append(i)\n",
    "        \n",
    "        index = -1\n",
    "        for word in s:\n",
    "            if word not in hash_set:\n",
    "                return False\n",
    "            \n",
    "            indexes = hash_set[word]\n",
    "            left = 0\n",
    "            right = len(indexes)\n",
    "            while left<right:\n",
    "                mid = left+(right-left)//2\n",
    "                if indexes[mid]>index:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            if left == len(indexes):\n",
    "                return False\n",
    "            index = indexes[left]\n",
    "        return True \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return True\n",
    "        if len(s) > len(t):\n",
    "            return False\n",
    "\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        f = [[True for _ in range(n )] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                f[i][j] = s[i] == t[j]\n",
    "                if i-1>=0 and j-1>=0:\n",
    "                    f[i][j] = f[i-1][j-1] and f[i][j]\n",
    "                if f[i][j]:\n",
    "                    break\n",
    "                  \n",
    "        return f[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        \"\"\"\n",
    "        # 双指针\n",
    "        l1 = len(s)\n",
    "        l2 = len(t)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < l1:\n",
    "            while i < l1 and j < l2 and t[j] == s[i]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            j += 1\n",
    "            if j >= l2: break\n",
    "        return i == l1\n",
    "        \"\"\"\n",
    "        # 动态规划\n",
    "        l1 = len(s)\n",
    "        l2 = len(t)\n",
    "        dp = [[False]*(l2+1) for i in range(l1+1)]\n",
    "        dp[0] = [True]*(l2+1)\n",
    "        for i in range(1, l1+1):\n",
    "            for j in range(1, l2+1):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return dp[l1][l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        t_remove = t[:]\n",
    "        for i_s in range(len(s)):\n",
    "            if s[i_s] in t_remove:\n",
    "                i_t = t_remove.index(s[i_s])\n",
    "                t_remove = t_remove[i_t+1:]\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        n, m = len(s), len(t)\n",
    "        i = j = 0\n",
    "        while i < n and j < m:\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return i == n\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        flag1=0\n",
    "        flag2=0\n",
    "        while flag1<len(s) and flag2<len(t):\n",
    "            if s[flag1]==t[flag2]:\n",
    "                flag1+=1\n",
    "                flag2+=1\n",
    "            else:\n",
    "                flag2+=1\n",
    "        return flag1==len(s)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        while i < len(s) and j < len(t):\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        if i == len(s):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bi_search(self, arr, x): \n",
    "        lt, rt = 0, len(arr)-1\n",
    "        if x >= arr[-1]: \n",
    "            return -1\n",
    "        while lt < rt:          # 有序列表arr中找到大于x的最小值\n",
    "            mid = (rt+lt) >> 1 \n",
    "            if arr[mid] <= x:\n",
    "                lt = mid + 1\n",
    "            else: \n",
    "                rt = mid \n",
    "        return arr[rt] \n",
    "            \n",
    "\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        slen, tlen = len(s), len(t) \n",
    "        alpha_idx = {}\n",
    "        for i in range(tlen): \n",
    "            if t[i] in alpha_idx:\n",
    "                alpha_idx[t[i]].append(i) \n",
    "            else: \n",
    "                alpha_idx[t[i]] = [i] \n",
    "        pre, flag = -1, 1 \n",
    "        for ch in s: \n",
    "            if ch not in alpha_idx: \n",
    "                return False \n",
    "            pre = self.bi_search(alpha_idx[ch], pre)\n",
    "            if pre == -1: \n",
    "                return False \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        i = j = 0        \n",
    "        while i < len(s) and  j < len(t):\n",
    "            if t[j] == s[i]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else: \n",
    "                j += 1\n",
    "        if i == len(s):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        si = 0\n",
    "        ti = 0\n",
    "        while si < len(s) and ti < len(t):\n",
    "            if s[si] == t[ti]:\n",
    "                si += 1\n",
    "                \n",
    "            ti += 1\n",
    "        return si == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        n,m = len(s),len(t)\n",
    "        i = j = 0\n",
    "        while i<n and j <m:\n",
    "            if s[i] == t[j]:\n",
    "                i+=1\n",
    "            j+=1\n",
    "        return i == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        i = j = 0\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        while i < n and j < m:\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return i == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        self.index = defaultdict(list)\n",
    "        for i,string in enumerate(t):\n",
    "            self.index[string].append(i)\n",
    "        print(self.index)\n",
    "        res = -1\n",
    "        for string in s:\n",
    "            if string not in self.index:\n",
    "                return False\n",
    "            else:\n",
    "                tmp = self.bisect_right(self.index[string],res)\n",
    "                if tmp<res or tmp==-1:\n",
    "                    return False\n",
    "                else:\n",
    "                    res = tmp\n",
    "                print(\"res:\",res)\n",
    "        return True\n",
    "\n",
    "    \n",
    "    def bisect_right(self,nums,target) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        while(left<right):\n",
    "            mid = left+(right-left)//2     \n",
    "            if nums[mid] <= target:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        if left>=len(nums):\n",
    "            return -1\n",
    "        return nums[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        index = {}\n",
    "        for i, ch in enumerate(t):\n",
    "            if ch not in index:\n",
    "                index[ch] = []\n",
    "            index[ch].append(i)\n",
    "\n",
    "        j = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in index:\n",
    "                return False\n",
    "            pos_list = index[s[i]]\n",
    "            left, right = 0, len(pos_list) - 1\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if pos_list[mid] < j:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            if left == len(pos_list) or pos_list[left] < j:\n",
    "                return False\n",
    "            j = pos_list[left] + 1\n",
    "\n",
    "        return True\n",
    "s = Solution()\n",
    "print(s.isSubsequence(\"abc\", \"ahbgdc\"))  # 输出 True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]\n",
    "        for i in range(1, len(s)+1):\n",
    "            for j in range(1, len(t)+1):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        if dp[-1][-1] == len(s):\n",
    "            return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]\n",
    "        for i in range(1, len(s) + 1):\n",
    "            for j in range(1, len(t) + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]     \n",
    "        if dp[-1][-1] == len(s):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        dp = [[0] * (len(t)+1) for _ in range(0, (len(s)+1))]\n",
    "        for i in range(1, (len(s)+1)):\n",
    "            for j in range(1, (len(t)+1)):\n",
    "                if s[i-1] == t[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 \n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                print(dp[i][j])\n",
    "        return dp[-1][-1] == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubsequence(self, s: str, t: str) -> bool:\n",
    "        dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]\n",
    "        for i in range(1, len(t) + 1):\n",
    "            for j in range(1, len(s) + 1):\n",
    "                if t[i - 1] == s[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        if dp[-1][-1] == len(s):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
